import java.util.Arrays;

public class MergeSortTest {

    public static void  chaFen(int[] array){
        if (array ==null){
            return;
        }
        int[] temp = new int[array.length];
        chaFen(array,0,array.length-1,temp);

    }
    public static void chaFen(int[] array,int left,int right,int[] temp){
        if (left < right){
            int mid = left +(right -left)/2;
            //递归控制指针
            //递归调用拆分数组
            chaFen(array,left,mid,temp);
            //右半部分
            chaFen(array,mid+1,right,temp);

            //合并排序
            heBingPaiXu(array,left,mid,right,temp);
        }
    }
    public static void heBingPaiXu(int[] array,int left,int mid,int right,int[] temp){
        //左数组的起始索引
        int l = left;
        //右数组的其实索引
        int r = mid+1;
        int t = 0;
        while (l <=mid && r<= right ){
            if (array[l] <= array[r]){
                temp[t++] = array[l++];
            }else {
                temp[t++] = array[r++];
            }
        }
        while (l<=mid){
            temp[t++] = array[l++];
        }
        while (r<=right){
            temp[t++] = array[r++];
        }
        //将数组copy到原文件中
        //重置指针
        t = 0;
        while(left <=right){
           array[left++] = temp[t++];
        }
    }
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前:");
        System.out.println(Arrays.toString(arr));

        chaFen(arr);

        System.out.println("\n排序后:");
        System.out.println(Arrays.toString(arr));
    }
}
